package com.itheima.algorithm.binarysearch;

public class BinarySearch {
    /*
     * 二分查找基础版
     *
     * Params: a - 带查找的升序数组
     *         target - 待查找的目标值
     * Returns:
     *         找到则返回索引
     *         找不到返回-1
     * */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        while (i <= j) {                    // 范围内有东西
            int m = (i + j) >>> 1;          // 使用无符号右移运算代替除法!
            if (target < a[m]) {            // 目标在左边
                j = m - 1;
            } else if (a[m] < target) {     // 目标在右边
                i = m + 1;
            } else if (target == a[m]) {    // 找到了
                return m;
            }
        }

        return -1;
    }
    /*
        问题1: 为什么 i<=j意味着区间内有为比较的元素, 而不是 i<j ?
            i==j  意味着 i,j 它们指向的元素也会参与比较
            i<j  只意味着 m 指向的元素参与比较
        问题2:(i + j) / 2 有没有问题?
            有 JAVA中的整数的最高位被视为符号位
            当一个两个正数相加 变为 一个最高位为1的数时 这时候/2会导致索引为负数
            而无符号右移(逻辑右移)是高位补0的 右移相当于/2了 但是符号位这时候一直为0 就是正数
        问题3: 都写成小于号有啥好处?
            人类默认左边小于右边的 比较容易观看代码
     */

    /*
        1 [2,3,4,5] 6 右侧没找到更差
        int i =0, j = a.length - 1;     2
        return -1;                      1
        元素个数        循环次数
         4-7              3     floor(log_2(4)) =  2 + 1
         8-15             4     floor(log_2(8)) =  3 + 1
         16-31            5     floor(log_2(16)) = 4 + 1
         32-63            6     floor(log_2(32)) = 2 + 1
         ...              ...

         循环次数L = floor(log_2(n)) + 1


         i <= j                     L+1
         int m = (i + j) >>> 1;     L
         target < a[m];             L
         i = m + 1;                 L

         (floor(log_2(n)) + 1) * 5 + 4

         (3) * 5 + 4 = 19*t

         (10 + 1) * 5 + 4 = 59*t
     */


    /*
     * 二分查找改动版
     *
     * Params: a - 带查找的升序数组
     *         target - 待查找的目标值
     * Returns:
     *         找到则返回索引
     *         找不到返回-1
     * */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0, j = a.length;        // 第一处
        while (i < j) {                 // 第二处
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;                  // 第三处
            } else if (a[m] < target) {
                i = m + 1;
            } else if (target == a[m]) {
                return m;
            }
        }

        return -1;
    }

    /*
     *  二分查找 Leftmost1
     *  求排名w
     */

    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else{
                // 记录候选位置
                candidate = m;
                j = m - 1;

            }
        }

        return candidate;
    }

    /*
     *  二分查找 Leftmost2
     *
     *  返回>=target的最靠左索引
     */
    public static int binarySearchLeftmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;

        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }
    /*
     *  二分查找 Rightmost
     *
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else{
                // 记录候选位置
                candidate = m;
                i = m + 1;

            }
        }
        return candidate;
    }
    /*
     *  二分查找 Rightmost
     *  返回<=target的最靠右索引
     */
    public static int binarySearchRightmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else{
                i = m + 1;
            }
        }
        return i-1;
    }





































}
